home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 16549 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.4 KB
  1. Path: topaz.cqu.edu.au!naderr
  2. From: naderr@topaz.cqu.edu.au
  3. Newsgroups: comp.lang.c++,comp.lang.c
  4. Subject: Josephus Problem
  5. Date: 11 Apr 96 16:52:09 +1000
  6. Organization: Central Queensland University, Australia
  7. Message-ID: <1996Apr11.165209@topaz>
  8. NNTP-Posting-Host: topaz.cqu.edu.au
  9.  
  10. Hi,
  11.  
  12.  
  13.  Brief Description of Josephus Problem:
  14.  
  15.  The program reads two positive integers, n and q.
  16.  Suppose n persons form a circle.  In clockwise order, we assign
  17.  numbers 1,2,...,n to them.  Starting at person 1 and counting clockwise
  18.  we remove the q-th person from the circles.  In the reduced circle,
  19.  we continue with the person following the person just removed and,
  20.  resume counting from 1 to q, again eliminating the q-th person.
  21.  This process is repeated until only one person remains: the program
  22.  outputs the number n, of this person.
  23.  
  24. I've recently coded this in C/C++ in two ways:
  25.  
  26. (1) With objects modelling the problem and deriving n, by 
  27. iterativley eliminating the q-th person. (it uses a double 
  28. circular linked list)
  29.  
  30.  
  31. (2) According to the description given in:
  32.  
  33.  
  34. =============================================================================
  35.         Functional Iteration and the Josephus Problem
  36.         A. M. Odlyzko and H. S. Wilf
  37.         Glasgow Math. J. 33 (1991), 235-240.
  38.  
  39.                   Andrew Odlyzko
  40.                   Mathematical Sciences Research Center
  41.                   Room 2C-355
  42.                   AT&T Bell Laboratories
  43.                   600 Mountain Avenue
  44.                   Murray Hill, NJ 07974, USA
  45.                   email: amo@research.att.com
  46.                   voice: 908-582-7286
  47.                   fax:   908-582-2379
  48.  
  49.     for WWW access, use the URL 
  50.     ftp://netlib.att.com/netlib/att/math/odlyzko/index.html.Z
  51.  
  52.     via ftp:  connect to netlib.att.com, login as anonymous,
  53.     give your e-mail address as password, and then do
  54.        binary
  55.        cd netlib/att/math/odlyzko
  56.  
  57. =============================================================================
  58.  
  59.  
  60. And the algorithm I have used is as follows:
  61.  
  62.  
  63. The authors give the following procedure for finding J(n):
  64.                                                       q
  65.  
  66.  
  67. [A]
  68.                            _            _ 
  69.                     (q)   |    q     (q) |              (q)
  70. Define a sequence  D    = | ------- D    |    ( n >= 1; D  = 1).
  71.                     n        q - 1   n-1                 0
  72.        _  _
  73.       |    |
  74. where |    | represents the 'ceiling' function.
  75.  
  76.  
  77. [B]
  78.                                          (q)
  79. Determine the least integer k, such that D   > (q - 1)n
  80.                                           k
  81.  
  82. [C]
  83.                                    (q)
  84. Then the answer is J(n) = qn + 1 - D
  85.                     q               k
  86.  
  87.  
  88. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  89.  
  90. Now,
  91.  
  92. where my problem lies is in [B]:
  93.  
  94. To search for k, I initialise k = 1 and increment it by 1 until the
  95. condition is satisfied.  This is ok for small n,q; but for larger
  96. values ( say n = 10000, q = 700 ) it is obviusly not :))
  97.  
  98. So, what I'm after is an algorithm that will minimise the iterations
  99. needed to determine k; a formula, anything :))
  100.  
  101. Any suggestions, pointers, help are greatly appreciated.
  102.  
  103. If replying to this message please do it to:
  104.  
  105.     naderr@topaz.cqu.edu.au
  106.  
  107. If you want the C/C++ code for both the simple modelling, using elimination
  108. of nodes in the circle, and the mathematical functional iterative solution
  109. program that I coded I'd be happy to forward them to you.
  110.  
  111.  
  112. Thanks in advance,
  113.  
  114.     Rob -
  115.